from offer.data_structure import LinkedNode


class Task25:
    def run(self, head1, head2):
        before_head = LinkedNode(None)
        tail = before_head

        while head1 is not None and head2 is not None:
            if head1.val < head2.val:
                tail.next = head1
                head1 = head1.next
            else:
                tail.next = head2
                head2 = head2.next
            tail = tail.next

        if head1 is None:
            tail.next = head2
        else:
            tail.next = head1

        return before_head.next
